#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_

#include <stddef.h>
#include <limits.h>

using ElementType = int;
class DynamicArray
{
public:
// 4个缺省函数：
    // 带参构造
    DynamicArray(size_t capacity = 15);
    // 拷贝构造
    DynamicArray(const DynamicArray &a);
    // 运算符重载
    DynamicArray &operator=(const DynamicArray &a);
    // 析构函数
    ~DynamicArray();

    // 数组大小
    size_t Size(); // 无符号长整型
    // 扩容接口（往大往小了扩都可以）
    void ReSize(size_t capacity);

    // 尾部插入
    void InsertTail(const ElementType &element);
    // 头部插入
    void InsertHead(const ElementType &element);
    // 中间插入
    void InsertByIndex(int index, const ElementType &element);
    
    // 按位置删除
    void RemoveByIndex(int index);
    // 按值删除
    void RemoveByElement(const ElementType &element);

    // 按位置查找
    ElementType *FindByIndex(int index);
    // 按值查找
    DynamicArray FindByElement(const ElementType &element);

    // 按位置修改
    void UpdateByIndex(int index, const ElementType &element);
    // 按值修改
    void UpdateByElement(const ElementType &oldValue, const ElementType &newValue);

    // 排序
    void Sort();
    // 去重算法
    void Duplicate();
    // 归并算法（合并两个已经有序的数列）
    DynamicArray Merge(const DynamicArray &a);
    
    // 找交集
    DynamicArray FdInterSctn(const DynamicArray &a);
    // 找并集
    DynamicArray FindUnionSet(const DynamicArray &a);
    // 找补集
    DynamicArray FindDifference(const DynamicArray &a);

    // 判断两个数列是否相等
    bool operator==(const DynamicArray &a);
    // 二分查找
    size_t BinarySearch(const ElementType &element);
    // 是否是子序列
    bool IsChild(const DynamicArray &a);
    // 是否是连续子序列
    bool IsCntnsChild(const DynamicArray &a);
    // 获取子序列
    DynamicArray subsequence(int index, size_t size);
    
    void show();
    
private:
    // 快排
    void FastSort(size_t start, size_t end, size_t depth, size_t MaxDepth);
    // 分组函数
    size_t Partition(size_t start, size_t end);
    // 插排
    void InsertSort(size_t start, size_t end);
    
    ElementType *array;
    size_t capacity;
    size_t size; 
    void(*freePtr)(ElementType);                // 数组元素释放的指针
    void(*PrintPtr)(ElementType);               // 打印元素的函数指针
    bool(*SortPtr)(ElementType, ElementType);   // 排序指针
    bool(*equalPtr)(ElementType, ElementType);  // 比较指针
}; 

#endif